package com.yiguang.algorithm.dp;

import java.util.ArrayList;
import java.util.List;

import com.alibaba.fastjson.JSON;

/*
	
	经典问题：
	354. 俄罗斯套娃信封问题 (隐晦的LIS)
	887. 鸡蛋掉落 (DP+二分)
	打家劫舍系列: (打家劫舍3 是树形DP)
	198. 打家劫舍
	213. 打家劫舍 II
	股票系列:
	121. 买卖股票的最佳时机
	122. 买卖股票的最佳时机 II
	123. 买卖股票的最佳时机 III
	188. 买卖股票的最佳时机 IV
	309. 最佳买卖股票时机含冷冻期
	714. 买卖股票的最佳时机含手续费
	字符串匹配系列
	72. 编辑距离
	44. 通配符匹配
	10. 正则表达式匹配
 */


public class Linear1Dp {
	
/**
 * 123. 买卖股票的最佳时机 III
 * 时间复杂度：O(n2)，循环运行了n(n-1)/2次
 * 空间复杂度：O(1)
 * 思路：遍历每个交易日，并用该交易日将所有交易日分为两段，分别求前后两段最大利润，取和。结果取最大
 * 意料之中，超出时间限制
 */
public static int maxProfit1(int[] prices) {
	int profit = 0; // 收益
	int min1 = Integer.MAX_VALUE;
	int profit1 = 0;
	for(int n=0; n<prices.length; n++) {
		int min2 = Integer.MAX_VALUE;
		int profit2 = 0;
		min1 = Math.min(min1, prices[n]);
		profit1 = Math.max(profit1, prices[n]-min1);
		for(int m=n+1; m<prices.length; m++) {
			min2 = Math.min(min2, prices[m]);
			profit2 = Math.max(profit2, prices[m]-min2);
		}
		if(profit1+profit2>profit) {
			profit = profit1+profit2;
		}
	}
	return profit;
    
}

/**
 * 优化
 * 123. 买卖股票的最佳时机 III
 * 时间复杂度：O(n2)，循环运行了n(n-1)/2次
 * 空间复杂度：O(1)
 * 思路：遍历每个交易日，并用该交易日将所有交易日分为两段，分别求前后两段最大利润，取和。结果取最大
 */
public static int maxProfit2(int[] prices) {
	int[] dp1 = new int[prices.length];
	int[] dp2 = new int[prices.length];
	int profit = 0; // 收益
	int min1 = Integer.MAX_VALUE;
	int profit1 = 0;
	int max2 = Integer.MIN_VALUE;
	int profit2 = 0;
	// 每个工作日结束最大收益
	for(int n=0; n<prices.length; n++) {
		min1 = Math.min(min1, prices[n]);
		profit1 = Math.max(profit1, prices[n]-min1);
		dp1[n] = profit1;
	}
	// 每个工作日开始到结束最大收益
	for(int n=prices.length-1; n>=0; n--) {
		max2 = Math.max(max2, prices[n]);
		profit2 = Math.max(profit2, max2-prices[n]);
		dp2[n] = profit2;
	}
	for(int n=0; n<prices.length-1; n++) {
		profit = Math.max(dp1[n]+dp2[n], profit);
	}
	return profit;
    
}

/*
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
 */
public static void main(String[] args) {
	// int[] nums = {1,2,4,2,5,7,2,4,9,0}; // 该测试用例可以看出买卖股票的最佳时机 III和 II的明显不同点
	int[] nums = {3,3,5,0,0,3,1,4};
	System.out.println(maxProfit1(nums));
	
}

	
}


